/* list, queue, stack lib
 * double list by @author chenxin<chenxin619315@gmail.com 
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "lqslib.h"

#ifdef DEBUG
	#define debug_print printf
#else
	#define debug_print
#endif

/*************************list***********************/
static int cel_link_init(cel_link_t *link); 
static cel_link_node_t *create_link_node(void *value, cel_link_node_t *prev, cel_link_node_t *next);
static int cel_link_destroy(cel_link_t *link, cel_release_callback_fn_t relfunc);
static void insert_before(cel_link_node_t *old, void *value);
static cel_link_node_t *get_node(cel_link_t *link, unsigned int idx);
static inline void cel_remove_node(cel_link_node_t *node);

inline unsigned int cel_link_size(cel_link_t *link)
{/*{{{*/
	if(link == NULL)
		return 0;

	return link->size;
}

/* Create a new cel link list */
cel_link_t *new_cel_link(void)
{
	cel_link_t *ptr = (cel_link_t *)malloc(sizeof(cel_link_t));
	if(ptr == NULL) {
		perror("new cel link");
		return NULL;
	}
	debug_print("malloc = %p\n", ptr);

	if(cel_link_init(ptr) == 0) {
		free(ptr);
		perror("new_cel_link");
	}

	return ptr;
}

/* Int 1 for success and 0 for failed */
static int cel_link_init(cel_link_t *link)
{
	link->size = 0;
	link->tail = create_link_node(NULL, NULL, NULL);
	if(link->tail == NULL) 
		return 0;

	link->head = create_link_node(NULL, NULL, link->tail);
	if(link->head == NULL) {
		free(link->tail);
		return 0;
	}

	link->tail->prev = link->head;
	 
	return 1;
}

/* Create a new link_node_entry */
static cel_link_node_t *create_link_node(void *value, 
							cel_link_node_t *prev, cel_link_node_t *next)
{
	cel_link_node_t *node = (cel_link_node_t *)malloc(sizeof(cel_link_node_t));
	if(node == NULL)
		return NULL;	

	node->value = value;
	node->prev = prev;
	node->next = next;

	debug_print("malloc = %p\n", node);
	return node;
}

/* free the specified cel link list, the remove callback function
 * maybe pass insite to finish the extra alloction free work */
void free_cel_link(cel_link_t **link, cel_release_callback_fn_t relfunc)
{
	if(link == NULL)
		return;
	if(*link != NULL)
	{
		cel_link_destroy(*link, relfunc);
		debug_print("free = %p\n", *link);
		free(*link);
		*link = NULL;
	}
}

/* Int 1 for success and 0 for failed */
static int cel_link_destroy(cel_link_t *link, cel_release_callback_fn_t relfunc)
{
	cel_link_node_t *node;
	cel_link_node_t *tmp;

	if(link != NULL)
	{
		node = link->head->next;
		while(node != link->tail)
		{
			/* invoke the callback function if it is not NULL */
			if(relfunc != NULL) {
				relfunc(node->value);
			}
			tmp = node;
			node = node->next;
			debug_print("free = %p\n", tmp);
			free(tmp);
		}
		debug_print("free = %p\n", link->head);
		free(link->head);
		link->head = NULL;

		debug_print("free = %p\n", link->tail);
		free(link->tail);
		link->tail = NULL;
	}
	return 1;
}

/* append element from the tail */
void cel_link_add_last(cel_link_t *link, void *value)
{
	insert_before(link->tail, value);
	link->size++;
}

/* add a element from the head */
void cel_link_add_first(cel_link_t *link, void *value)
{
	insert_before(link->head->next, value);
	link->size++;
}

/* insert the element at a specified position */
void cel_link_insert(cel_link_t *link, unsigned int idx, void *value)
{
	cel_link_node_t *o = get_node(link, idx);
	if(o != NULL)
	{
		insert_before(o, value);
		link->size++;
	}
}

/* insert a element before the specified node */
static void insert_before(cel_link_node_t *old, void *value)
{
	cel_link_node_t *o = create_link_node(value, old->prev, old);
	if(o != NULL)
	{
		o->prev->next = o;
		o->next->prev = o;
	}
}

/* get the node at a specified position */
static cel_link_node_t *get_node(cel_link_t *link, unsigned int idx)
{
	//register unsigned int i;
	unsigned int i;
	cel_link_node_t *p = NULL;

	if(idx >= link->size)
		return NULL;

	/* find the node */
	if(idx > link->size / 2)
	{
		p = link->tail;
		for(i = link->size; i >= idx; i--)
			p = p->prev;
	}
	else
	{
		p = link->head;
		for(i = 0; i < idx; i++)
			p = p->next;
	}
	return p;
}

/* remove the element from the head */
void * cel_link_remove_first(cel_link_t *link)
{
	void *v;
	cel_link_node_t *o;

	if(link->size == 0)
		return NULL;

	o = link->head->next;
	v = o->value;
	cel_remove_node(o);
	debug_print("free = %p\n", o);
	free(o);
	link->size--;

	return v;
}

/* remove the element from the tail */
void *cel_link_remove_last(cel_link_t *link)
{
	void *v;
	cel_link_node_t *o;

	if(link->size == 0)
		return NULL;

	o = link->tail->prev;
	v = o->value;
	cel_remove_node(o);
	debug_print("free = %p\n", o);
	free(o);
	link->size--;

	return v;
}

/* remove the element at a specified position */
void *cel_link_remove(cel_link_t *link, unsigned int idx)
{
	void *v;
	cel_link_node_t *o = get_node(link, idx);
	if(o == NULL)
		return NULL;

	/* remove the node */
	v = o->value;
	cel_remove_node(o);
	debug_print("free = %p\n", o);
	free(o);

	link->size--;
	return v;
}

/* remove the element equals the given one */
void *cel_link_remove_obj(cel_link_t *link, void *value, cel_compare_fn_t comp)
{
	void *v;
	cel_link_node_t *o;

	for(o = link->head->next; o != link->tail; o = o->next)
	{
		if(value == o->value || comp(value, o->value) == 0)
		{
			v = o->value;
			cel_remove_node(o);
			debug_print("free = %p\n", o);
			free(o);
			link->size--;

			return v;
		}
	}

	return NULL;
}

static inline void cel_remove_node(cel_link_node_t *node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
}


/* get the element at the specified position */
void *cel_link_get(cel_link_t *link, unsigned int idx)
{
	cel_link_node_t *o = get_node(link, idx);

	if(o == NULL)
		return NULL;

	return o->value;
}

/* set the element at the specified position with the specified value */
void *cel_link_set(cel_link_t *link, unsigned int idx, void *value)
{
	void *v;
	cel_link_node_t *old = get_node(link, idx);

	if(old == NULL)
		return NULL;

	v = old->value;
	old->value = value;

	return v;
}

/* search the element and replace it with a new one */
/* 查找link的node中value的值等于@search的(comp比较)
 * 然后用value的值替换找到node中的value */
void *cel_link_set_obj(cel_link_t *link, void *search, 
							void *value, cel_compare_fn_t comp)
{
	void *v;
	cel_link_node_t *o;

	for(o = link->head->next; o != link->tail; o = o->next)
	{
		if(search == o->value || comp(search, o->value) == 0)
		{
			v = o->value;
			o->value = value;
			return v;
		}
	}
	return NULL;
} /*}}}*/

/*************************queue**********************/

inline cel_queue_t *new_cel_queue(void)
{
	return new_cel_link();
}

inline void free_cel_queue(cel_queue_t **queue, cel_release_callback_fn_t relfunc)
{
	free_cel_link(queue, relfunc);
}

inline unsigned int cel_queue_length(cel_queue_t *queue)
{
	return cel_link_size(queue);
}

inline void cel_queue_en(cel_queue_t *queue, void *value)
{
	cel_link_add_first(queue, value);
}

inline void *cel_queue_de(cel_queue_t *queue)
{
	return cel_link_remove_last(queue);
}


/*************************stack**********************/

inline cel_stack_t *new_cel_stack(void)
{
	return new_cel_link();
}

inline void free_cel_stack(cel_stack_t **stack, cel_release_callback_fn_t relfunc)
{
	free_cel_link(stack, relfunc);
}

inline unsigned int cel_stack_depth(cel_stack_t *stack)
{
	return cel_link_size(stack);
}

inline void cel_stack_push(cel_stack_t *stack, void *value)
{
	cel_link_add_first(stack, value);
}

inline void *cel_stack_pop(cel_stack_t *stack)
{
	return cel_link_remove_first(stack);
}


